package offer_test_60;

import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction;

//正则表达式匹配，请实现一个函数用来匹配包含“.”和“*”的正则表达式模式中的“.”代表任意一个字符，
//而“*”表示它前面的字符可以出现任意次（包括0次）。本题中，匹配指的是字符串的所有字符匹配整个模式。
//例如字符串“aaa”与模式“a.a”匹配，和"ab*ac*a"匹配，但是与"aa.a"以及"ab*a"均不匹配。
public class thirteen_StringPattern {
	public static void main(String[] args) {
		String input1 = "aaa";
		String input2 = "aaa";
		String input3 = "aaa";
		String input4 = "aab";
		String p1 = "ab*ac*a";
		String p2 = "ab*a*c*a";
		String p3 = ".*";
		String p4 = "c*a*b";
		String rs1 = "true";
		String rs2 = "true";
		String rs3 = "true";
		String rs4 = "true";
		 System.out.println(isPattern(input1, p1)+" "+rs1);
		 System.out.println(isPattern(input2, p2)+" "+rs2);
		System.out.println(isPattern(input3, p3) + " " + rs3);
		 System.out.println(isPattern(input4, p4)+" "+rs4);
	}

	public static boolean isPattern(String str, String pattern) {
		char[] strarray = str.toCharArray();
		char[] patternarray = pattern.toCharArray();
		return judge(strarray, patternarray, 0, 0);
	}

	public static boolean judge(char[] array, char[] pattern, int strbegin,
			int patternbegin) {
		boolean judge = false;
		// 终止条件
		if (strbegin > array.length - 1 && patternbegin > pattern.length - 1)
			return true;

		if (strbegin <= array.length - 1 && patternbegin > pattern.length - 1)
			return false;
		if (patternbegin < pattern.length - 1
				&& pattern[patternbegin + 1] == '*') {
			if (pattern[patternbegin] == '.'
					|| array[strbegin] == pattern[patternbegin]) {
				return judge(array, pattern, strbegin + 1, patternbegin + 2)
						|| judge(array, pattern, strbegin + 1, patternbegin)
						|| judge(array, pattern, strbegin, patternbegin + 2);
			}
			else{
				return judge(array, pattern, strbegin, patternbegin+2);
			}
		}
		if(pattern[patternbegin] == '.'
				|| array[strbegin] == pattern[patternbegin]){
			return judge(array, pattern, strbegin+1, patternbegin+1);
		}
		return judge;
	}
}
